Theory of Computation
Q151.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?Q152.
If L is a regular language over \Sigma =\{a,b\}, which one of the following languages is NOT regular ?Q153.
A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?Q154.
For \Sigma =\{a,b\}, let us consider the regular language L=\{x|x=a^{2+3k} \; or \; x=b^{10+12k}, k\geq 0\}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?Q155.
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?Q156.
Which of the following are regular sets? I. \{a^{n}b^{2m}|n\geq 0,m\geq 0\} II. \{a^{n}b^{m}|n=2m\} III. \{a^{n}b^{m}|n\neq m\} IV. \{xcy|x,y,\in \{a,b\}^*\}Q159.
Consider the languages L_{1}=\phi abd L_{2}=\{a\}. Which one of the following represents L_{1} L_{2}^{*} \cup L_{1}^{*}?